The term “Persistent Data Item” or “PDI” as used herein is defined to be a data item having associated with it a value which changes over time, in particular when updated by an application program, and which is required to retain its state between such updates, particularly when the application is not running and when power is removed intentionally, when the application is switched off, or accidentally, for example because of a power failure or removal from a power source.
Computer programs operate by reading and updating the values of variables. For variables in RAM, this presents little difficulty as the values can be rewritten as often as necessary and reading and writing are fast. When the program is not running, its state must be stored in more persistent memory.
On small computer platforms such as smart cards, there is little RAM and the persistent memory often takes the form of EEPROM or Flash memory. This memory has the property that, once a bit has been changed, it cannot be changed again until the whole segment is erased. In EEPROM, the segment size may be as small as a single byte (8 bits) and the memory can be treated essentially as very slow RAM. In flash memory, the segments are generally large (e.g. 64 KB) for silicon area efficiency and the erase operation is slow. Also, the memory will eventually wear out after some number of erase cycles (say 100,000 for high quality Flash). The advantage of flash memory is that it is faster and much more can be packed into a given chip area so there is more storage space, but it is harder than EEPROM to use efficiently.
Consider a smart card application which keeps a record of the date and time (obtained from a card reader terminal, perhaps) on each occasion that it runs and checks the interval between runs. This could be used for a security function, such as enforcing a daily withdrawal limit for a cash card. Every time it runs, it must read the old date, check it and store the new date. The date is therefore a PDI. If the date were stored in the same location each time it changes, the whole 64K block would first have to be erased because of the physical memory limitations and this would take a long time and rapidly wear out the flash memory.
Instead, each time the new date is written, it must be stored in a new area of memory. It is assumed that this program has to share the flash memory with other programs, so it is not efficient to pre-allocate a large block of flash memory just for this one application. In other words, there may be many PDIs in the system and they might be updated at different rates, depending on the applications running.
A known arrangement for storing PDIs builds a linked chain of values for each PDI as illustrated in FIG. 1 of the accompanying drawings. The first element of the chain is at a known address. For the specific application mentioned above, each element of the chain stores a value for the date record and has a space for a pointer to the next item in the chain. The last chain element will have a pointer value equal to the erased memory pattern (FFFF in hexadecimal in this model where the erased state of each bit is 1 or 0000 in the complementary model where the erased state of each bit is 0). To read the current date, reading starts at the beginning of the chain and follows pointers until one is reached with value FFFF. To add a new date, a new chain element is created with the new value and an empty pointer. The address is then stored over the pointer part of the previous last-element.
When the block is full, only the most recent values for each PDI need to be copied to a fresh block, after which the old block is erased. This is referred to as “garbage collection”. When garbage collecting, the last value in the chain is copied to the new block and used as the start of the new chain.
If power is removed from a flash memory during a write cycle, there is a danger that the operation will be incomplete and that an inconsistent state will be available when power is reapplied. In the case of a contactless smart card having flash memory, the card itself does not have any power supply but relies on receiving power from a card reader when presented thereto. If the card is removed from the reader during a write operation to the flash memory, the power supply may be interrupted during the write cycle so that the data actually stored are different from the data which were intended to be stored.
For example, in a typical flash memory, the erased state of each bit is 1 and each bit can be changed to 0 during a write cycle but the reverse change from 0 to 1 can only be achieved by erasing a whole page or segment at a time. Also, if a write cycle is interrupted, each bit which is to be changed from 1 to 0 will either change to 0 or remain at 1. Typically, a whole word comprising 16 bits is written in parallel to the flash memory. When a write operation is interrupted by power loss, some or all of the requested changes from 1 to 0 may have occurred but it is impossible to identify which changes have occurred and which (if any) have not. When power is applied again, the smart card cannot tell whether the stored data has been corrupted because of power loss during a write cycle.
In the case of the linked chain as illustrated in FIG. 1 of the accompany drawings and as described hereinbefore or in the case of the arrangement disclosed in British patent application no. 0205573.9 (the contents of which are incorporated herein by reference), which describes an improved arrangement, the current value of each data item is the last one in the linked chain or list. If power fails when the pointer to the last value is being written into the flash memory, it may not be possible to retrieve the last value when power is restored. Any application relying on such a last value will therefore not function correctly or may not function at all.